1. Field of the Invention
The invention relates to error correction codes, and more particularly to encoding and decoding of error correction codes.
2. Description of the Related Art
After data is converted into an error correction code, if errors occur in the error correction code, the data without errors can be recovered according to a parity of the error correction code. Data of a transmitter in a communication system is often encoded to obtain an error correction code to be transmitted to a receiver of a communication system. After the receiver of the communication system receives the error correction code, if errors occur in the error correction code due to a transmission process, the receiver can correct the errors of the received error correction code and then recover the data without errors. Similarly, a data storage system often encodes data to obtain an error correction code to be stored in a storage medium. When errors occur in the error correction code stored in the storage medium, the data storage system can decode the error correction code to recover the data without errors. An error correction code may be a Bose, Ray-Chaudhuri, and Hocquenghem (BCH) code or a Reed-Solomon (RS) code. Data to be stored in a flash memory is often converted into a BCH code, and data to be stored in an optical disk is often converted to a RS code.
After a data storage system retrieves an error correction code from a storage medium, the error correction code must be decoded to recover data stored therein. Referring to FIG. 1, a flowchart of a conventional method 100 for decoding an error correction code is shown. First, a decoder receives an error correction code (step 102). The decoder then calculates a plurality of syndromes according to a parity of the error correction code (step 104). The decoder then determines whether the syndromes are all equal to zero (step 106). When the syndromes are all equal to zero, no error has occurred in the error correction code, and no correction is required. When some of the syndromes are not equal to zero, errors have occurred in the error correction code, and the error correction code requires correction. First, the decoder calculates a plurality of coefficients of an error location polynomial according to the syndromes (step 108). The decoder then performs a Chien search to find a plurality of roots of the error location polynomial according to the coefficients of the error location polynomial (step 110). Because the roots of the error location polynomial indicate the positions of error bits in the error correction code, the decoder can then correct the error bits of the error correction code according to the roots (step 112), and then obtain an error correction code without errors.
Calculation of the coefficients of the error location polynomial in step 108 requires a long time period. Similarly, performing the Chien search in step 110 also requires a long time period to calculate the roots of the error location polynomial. According to the conventional method 100, the steps 108 and 110 are performed to correct error bits of the error correction code when any of the syndromes are not equal to zero, thus causing a delay in the decoding process and degrading system performance. When some of the syndromes are not equal to zero, if the error correction code is corrected in a method that avoids calculation of the coefficients and the roots of the error location polynomial in steps 108 and 110, respectively, the delay period of the decoding process may be reduced, and performance of the decoder and the data storage system may be improved. Thus, a new method for encoding and decoding an error correction code is required.